package com.tsx.leetcode.hot100.other;

import java.util.Arrays;

public class CandyDistribution {

    public static int minCandies(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }

        int n = arr.length;
        int[] candies = new int[n];
        
        // 初始化每个小朋友至少有一颗糖果
        Arrays.fill(candies, 1);

        // 从左到右遍历
        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        // 从右到左遍历
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }

        // 检查首位元素是否满足条件
        if (arr[0] > arr[n - 1]) {
            candies[0] = Math.max(candies[0], candies[n - 1] + 1);
        } else if (arr[n - 1] > arr[0]) {
            candies[n - 1] = Math.max(candies[n - 1], candies[0] + 1);
        }

        // 计算总糖果数
        int totalCandies = 0;
        for (int candy : candies) {
            totalCandies += candy;
        }

        return totalCandies;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 5, 4, 3, 2};
        System.out.println(minCandies(arr));  // 输出结果
    }
}
